// 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

// 示例 1:

// 输入: "abab"

// 输出: True

// 解释: 可由子字符串 "ab" 重复两次构成。
// 示例 2:

// 输入: "aba"

// 输出: False
// 示例 3:

// 输入: "abcabcabcabc"

// 输出: True

// 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

#include <string>
#include <vector>

using std::vector;
using std::string;

class Solution1 {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i = n / 2; i >= 1; --i) { // 子串长度不能大于总长度的一半
            if (n % i == 0) { // 子串长度要能被总长度整除
                int c = n / i; // 原字符串分成c段
                string t{};
                for (int j{0}; j < c; ++j)
                    t += s.substr(0, i); // 拼接c段子串
                if (t == s)
                    return true; // 只要有一种情况符合就可以
            }
        }
        return false;
    }
};

// KMP
class Solution2 {
public:
    bool repeatedSubstringPattern(string s) {
        int i{1};
        int j{0};
        int n = s.size();
        vector<int> dp(n+1, 0);
        while (i < n) {
            if (s[i] == s[j]) 
                dp[++i] = ++j;
            else if (j == 0) 
                ++i;
            else 
                j = dp[j];
        }
        return dp[n] && (dp[n] % (n - dp[n]) == 0);
    }
};

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i{0}; i < n / 2; ++i) {
            if (n % (i + 1) != 0) continue;
            int m = n / (i + 1); // m段
            string subStr = s.substr(0, i+1);
            string s1{};
            while (m--) {
                s1 += subStr;
            }
            if (s1 == s) return true;
        }
        return false;
    }
};

/* 枚举
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i{1}; i * 2 <= n; ++i) {
            if (n % i == 0) {
                bool match{true};
                for (int j{i}; j < n; ++j) {
                    if (s[j] != s[j - i]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
};

/* 字符串匹配
使用语言自带得字符串查找函数
将两个 s 连在一起，并移除第一个和最后一个字符。如果 s 是该字符串的子串，那么 s 就满足题目要求。
*/
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};

/* KMP算法
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    bool kmp(const string& query, const string& pattern) {
        int n = query.size();
        int m = pattern.size();
        vector<int> fail(m, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern[j + 1] != pattern[i]) {
                j = fail[j];
            }
            if (pattern[j + 1] == pattern[i]) {
                fail[i] = j + 1;
            }
        }
        int match = -1;
        for (int i = 1; i < n - 1; ++i) {
            while (match != -1 && pattern[match + 1] != query[i]) {
                match = fail[match];
            }
            if (pattern[match + 1] == query[i]) {
                ++match;
                if (match == m - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    bool repeatedSubstringPattern(string s) {
        return kmp(s + s, s);
    }
};

/* KMP算法
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    bool kmp(const string& pattern) {
        int n = pattern.size();
        vector<int> fail(n, -1);
        for (int i = 1; i < n; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern[j + 1] != pattern[i]) {
                j = fail[j];
            }
            if (pattern[j + 1] == pattern[i]) {
                fail[i] = j + 1;
            }
        }
        return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
    }

    bool repeatedSubstringPattern(string s) {
        return kmp(s);
    }
};